////
//// Created by mac on 2023/10/26.
////
////
//// Created by mac on 2023/10/26.
////
//
//#include <iostream>
//#include <vector>
//#include <string>
//
//

// 正则表达式匹配
//class Solution
//{
//public:
//    bool isMatch(string s, string p)
//    {
//        // 1、建表
//        int m = s.size(), n = p.size();
//        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
//
//        // 2、初始化
//        s = ' ' + s;
//        p = ' ' + p;
//        dp[0][0] = true;
//        for(int j = 2; j <= n; j += 2)
//            if(p[j] == '*') dp[0][j] = true;
//            else break;
//
//        // 3、填表
//        for(int i = 1; i <= m; ++i)
//            for(int j = 1; j <= n; ++j)
//                if(p[j] == '*')
//                    dp[i][j] = dp[i][j-2] || (p[j-1] == s[i] || p[j-1] == '.') && dp[i-1][j];
//                else
//                    dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i-1][j-1];
//
//        // 4、返回值
//        return dp[m][n];
//    }
//};
//using namespace std;
//
//// 通配符匹配
//class Solution
//{
//public:
//    static bool isMatch(string s, string p)
//    {
//        // 1、建表
//        int m = s.size(), n = p.size();
//        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
//        // 2、初始化
//        s = ' ' + s;
//        p = ' ' + p;
//
//        for(int j = 0; j <= n; ++j)
//        {
//            if(j == 0)
//                dp[0][j] = true;
//            else
//            if(p[j] == '*' && dp[0][j - 1] == true) dp[0][j] = true;
//
//            // cout << dp[0][0] << endl;
//        }
//        // 3、填表
//        for(int i = 1; i <= m; ++i)
//        {
//            for(int j = 1; j <= n; ++j)
//            {
//                if(p[j] == '?')
//                    if(dp[i - 1][j - 1]) dp[i][j] = true;
//                    else if(p[j] == '*')
//                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
//                    else
//                    if(s[i] == p[j] && dp[i - 1][j - 1]) dp[i][j] = true;
//            }
//        }
//        //  4、返回值
//        cout << p[1] << endl;
//        cout << dp[0][1] << endl;
//        cout << dp[1][1] << endl;
//        return dp[m][n];
//    }
//};
//
//int main()
//{
//    Solution::isMatch(string("aa"), string("*"));
//    return 0;
//}